package com.leetcode.partition1;

import com.leetcode.common.TreeNode;

import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/18 9:32
 */
public class LC100相同的树 {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        return iteration(p, q);
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1, null, new TreeNode(2));
        TreeNode n2 = new TreeNode(1, new TreeNode(2), null);
        System.out.println(new LC100相同的树().isSameTree(n1, n2));
    }

    private boolean iteration(TreeNode p, TreeNode q) {
        Stack<TreeNode> s = new Stack<>();
        s.push(p);
        s.push(q);
        while (!s.isEmpty()) {
            TreeNode cur1 = s.pop();
            TreeNode cur2 = s.pop();
            if ((cur1 == null && cur2 != null) || (cur1 != null && cur2 == null)) return false;
            if (cur1 == null && cur2 == null) continue;
            if (cur1.val != cur2.val) return false;
            s.push(cur2.right);
            s.push(cur1.right);
            s.push(cur2.left);
            s.push(cur1.left);
        }
        return true;
    }
    
    private boolean recursion(TreeNode p, TreeNode q) {
        if ((p == null && q != null) || (p != null && q == null)) return false;
        if (p == null && q == null) return true;
        if (p.val != q.val) return false;
        return recursion(p.left, q.left) && recursion(p.right, q.right);
    }
}
